package everydayGrade.t0;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-11-17-0:03
 * @Description: 1.0
 */
public class T2736 {
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length, m = queries.length;
        int[][] num = new int[n][2];
        for (int i = 0; i < n; i++) {
            num[i][0] = nums1[i];
            num[i][1] = nums2[i];
        }
        Arrays.sort(num, (a, b) -> b[0] - a[0]);
        Integer[] qid = new Integer[m];
        for (int i = 0; i < m; i++) {
            qid[i] = i;
        }
        Arrays.sort(qid, (a, b) -> queries[b][0] - queries[a][0]);
        List<int[]> list = new ArrayList<>();
        int[] res = new int[m];
        int j = 0;
        for (int i : qid) {
            int x = queries[i][0], y = queries[i][1];
            for (; j < n && num[j][0] >= x; j++) {
                while (!list.isEmpty() && list.get(list.size() - 1)[1] <= num[j][0] + num[j][1]) {
                    list.remove(list.size() - 1);
                }
                if (list.isEmpty() || list.get(list.size() - 1)[0] < num[j][1]) {
                    list.add(new int[]{num[j][1], num[j][0] + num[j][1]});
                }
            }
            int p = lowerBound(list, y);
            res[i] = p < list.size() ? list.get(p)[1] : -1;
        }
        return res;
    }

    public int lowerBound(List<int[]> list, int target) {
        int left = -1, right = list.size();
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (list.get(mid)[0] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
